/*
 * $Id: BaseString.hpp 59 2009-02-19 10:30:57Z hyunghwan.chung $
 *
   Copyright 2005-2009 Chung, Hyung-Hwan.

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an  BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
 */

#ifndef _XP_BAS_BASESTRING_CLASS_
#define _XP_BAS_BASESTRING_CLASS_

#include <xp/types.h>
#include <xp/macros.h>
#include <xp/bas/memory.h>
#include <xp/bas/stdarg.h>
#include <xp/Hashable.hpp>
#include <xp/RefCounted.hpp>


XP_BEGIN_NAMESPACE2 (xp, bas)

template <typename char_type, typename OPSET> class BaseString;

template <typename char_type, typename OPSET>
class BaseStringData: public RefCounted
{
protected:
	friend class BaseString<char_type,OPSET>;

	typedef BaseStringData<char_type,OPSET> ThisType;

	BaseStringData (xp_size_t capacity, const char_type* str, xp_size_t offset, xp_size_t size)
	{
		// xp_assert (capacity >= size);
		if (capacity < size) capacity = size;
		this->buffer = new char_type[capacity + 1];
		xp_memcpy (this->buffer, str + offset, size * XP_SIZEOF(char_type));
		this->buffer[size] = (char_type)0;
		this->size = size;
		this->capacity = capacity;
	}
	BaseStringData (xp_size_t capacity, char_type c, xp_size_t size)
	{
		//xp_assert (capacity >= size);
		if (capacity < size) capacity = size;
		this->buffer = new char_type[capacity + 1];
		this->buffer[size] = (char_type)0;
		this->size = size;
		this->capacity = capacity;
		while (size > 0) this->buffer[--size] = c;
	}


public:
	~BaseStringData () 
	{
		xp_assert (this->buffer != XP_NULL);
		delete[] this->buffer;
	}

protected:	
	ThisType* copy ()
	{
		return new ThisType (this->capacity, this->buffer, 0, this->size);
	}
	ThisType* copy (xp_size_t capacity)
	{
		return new ThisType (capacity, this->buffer, 0, this->size);
	}

	void growBy (xp_size_t inc)
	{
		if (inc > 0) 
		{
			xp_size_t newcapa = this->capacity + inc;
			char_type* tmp = new char_type[newcapa + 1];
			xp_memcpy (tmp, this->buffer, this->size * XP_SIZEOF(char_type));
			delete[] this->buffer;
			this->buffer = tmp;
			this->buffer[this->size] = (char_type)0;
			this->capacity = newcapa;
		}
	}

	xp_size_t capacity;	
	xp_size_t size;
	char_type* buffer;	
};
	
template <typename char_type, typename OPSET>
class BaseString: public Hashable
{
public:
	enum 
	{
		DFL_CAPACITY = 128,
		INVALID_INDEX = ~(xp_size_t)0
	};

	class GrowthPolicy 
	{
	public:
		enum Type
		{
			ABSOLUTE,
			PERCENT
		};

		GrowthPolicy (Type type = ABSOLUTE, xp_size_t value = 0): type (type), value (value) {}

		Type type;
		xp_size_t value;
	};

	typedef BaseString<char_type,OPSET> ThisType;
	typedef BaseStringData<char_type,OPSET> StringData;

	BaseString ()
	{
		data = new StringData (round_capacity(DFL_CAPACITY), XP_NULL, 0, 0);
		this->data->ref ();
	}
	BaseString (xp_size_t capacity)
	{
		data = new StringData (round_capacity(capacity), XP_NULL, 0, 0);
		this->data->ref ();
	}
	BaseString (const char_type* str)
	{
		xp_size_t len = ThisType::lengthOf (str);
		data = new StringData (round_capacity(len), str, 0, len);
		this->data->ref ();
	}
	BaseString (const char_type* str, xp_size_t offset, xp_size_t size)
	{
		data = new StringData (round_capacity(size), str, offset, size);
		this->data->ref ();
	}
	BaseString (char_type c, xp_size_t size)
	{
		data = new StringData (round_capacity(size), c, size);
		this->data->ref ();
 	}
	BaseString (const ThisType& str)
	{
		data = str.data;
		this->data->ref ();
	}

	~BaseString () 
	{
		this->data->deref ();
	}

	const GrowthPolicy& growthPolicy () const
	{
		return this->growth_policy;
	}

	///
	/// The setGrowthPolicy() function sets how to grow the buffer capacity
	/// when more space is needed. 
	///
	/// The sample below doubles the capacity of the current buffer when necessary.
	/// \code
	///   xp::bas::String x;
	///   x.setGrowthPolicy (xp::bas::String::GrowthPolicy (xp::bas::String::GrowthPolicy::PERCENT, 100));
	///   for (int i = 0; i < 2000; i+=3)
	///   {
	///       x.appendFormat (XP_T("%d %d %d "), i+1, i+2, i+3);
	///   }
	/// \endcode
	void setGrowthPolicy (const GrowthPolicy& pol)
	{
		this->growth_policy = pol;
	}

	xp_size_t size () const 
	{
		return this->data->size;
	}
	xp_size_t length () const 
	{
		return this->data->size;
	}
	xp_size_t capacity () const 
	{
		return this->data->capacity;
	}

	operator const char_type* () const 
	{
		return this->data->buffer;
	}

	const char_type* buffer() const
	{
		return this->data->buffer;
	}

	xp_size_t hashCode () const
	{
		// keep this in sync with hashCode of BasePtrString<char_type>
		return Hashable::hashCode (
			this->data->buffer, this->data->size * XP_SIZEOF(char_type));
	}

	const char_type& operator[] (xp_size_t index)
	{
		xp_assert (index < this->data->size);

		if (this->data->isShared()) 
		{
			StringData* t = this->data->copy ();
			this->data->deref (); this->data = t; this->data->ref ();
		}
		return this->data->buffer[index];
	}

	ThisType& operator= (const ThisType& str)
	{
		if (this->data != str.data) 
		{
			this->data->deref ();
			this->data = str.data;
			this->data->ref ();
		}
		return *this;
	}
	ThisType& operator= (const char_type* str)
	{
		if (this->data->buffer != str)
		{
			this->remove ();
			this->insert (0, str);
		}
		return *this;
	}
	ThisType& operator= (const char_type c)
	{
		this->remove ();
		this->insert (0, &c, 0, 1);
		return *this;
	}

	ThisType& operator+= (const ThisType& str)
	{
		this->insert (this->data->size, str.data->buffer, 0, str.data->size);
		return *this;
	}
	ThisType& operator+= (const char_type* str)
	{
		this->insert (this->data->size, str);
		return *this;
	}
	ThisType& operator+= (const char_type c)
	{
		this->insert (this->data->size, &c, 0, 1);
		return *this;
	}

	bool operator== (const ThisType& str) const
	{
		if (this->data->size != str.data->size) return false;
		return xp_memcmp (
			this->data->buffer, str.data->buffer,
			XP_SIZEOF(char_type) * this->data->size) == 0;
	}

	bool operator!= (const ThisType& str) const
	{
		return !operator== (str);
	}

	bool operator== (const char_type* str) const
	{
		return ThisType::compare (this->data->buffer, this->data->size, str) == 0;
	}
	bool operator!= (const char_type* str) const
	{
		return ThisType::compare (this->data->buffer, this->data->size, str) != 0;
	}

	//
	// TODO: comparison, hash, trim, case-converting, etc
	// utf-8 encoding/decoding
	//

	char_type& charAt (xp_size_t index) 
	{
		xp_assert (index < this->data->size);
		return this->data->buffer[index];
	}
	const char_type& charAt (xp_size_t index) const 
	{
		xp_assert (index < this->data->size);
		return this->data->buffer[index];
	}
	void setCharAt (xp_size_t index, char_type c)
	{
		xp_assert (index < this->data->size);

		if (this->data->isShared()) 
		{
			StringData* t = this->data->copy ();
			this->data->deref (); this->data = t; this->data->ref ();
		}
		this->data->buffer[index] = c;
	}
	
	void insert (xp_size_t index, const char_type* str, xp_size_t offset, xp_size_t size)
	{
		if (size <= 0) return;
		if (index >= this->data->size) index = this->data->size;
	
		//
		// When the same instance is inserted as in n.insert(index, n) which
		// finally calls n.insert(index. n.this->data->buffer, 0, n.this->data->size),
		// if n is not shared and should be copied, calling deref to it 
		// immediately after it's copied will destroy n.data refered to by
		// str/offset/size. So the deref must be called after copying is
		// done.
		//
	
		StringData* old_data = XP_NULL;
		xp_size_t new_size = this->data->size + size;
	
		if (this->data->isShared()) 
		{
			StringData* t;
			if (new_size > this->data->capacity) 
				t = this->data->copy (this->data->capacity + calc_new_inc_for_growth(new_size - this->data->capacity));
			else t = this->data->copy ();
			//this->data->deref (); this->data = t; this->data->ref ();
			old_data = data; this->data = t; this->data->ref ();
		}
		else if (new_size > this->data->capacity) 
		{
			StringData* t = this->data->copy (this->data->capacity + calc_new_inc_for_growth(new_size - this->data->capacity));
			//this->data->deref (); this->data = t; this->data->ref ();
			old_data = data; this->data = t; this->data->ref ();
		}
		
		char_type* p = this->data->buffer + index;
		xp_memmove (p + size, p, (this->data->size - index) * XP_SIZEOF(char_type));
		xp_memcpy (p, str + offset, size * XP_SIZEOF(char_type));
	
		this->data->size = new_size;
		this->data->buffer[new_size] = (char_type)0;
	
		if (old_data) old_data->deref ();
	}
	void insert (xp_size_t index, const char_type* str)
	{
		this->insert (index, str, 0, ThisType::lengthOf(str));
	}
	void insert (xp_size_t index, const char_type c)
	{
		this->insert (index, &c, 0, 1);
	}
	void insert (xp_size_t index, const ThisType& str, xp_size_t offset, xp_size_t size)
	{
		xp_assert (offset + size <= str.data->size);
		this->insert (index, str.data->buffer, offset, size);
	}
	void insert (xp_size_t index, const ThisType& str)
	{
		this->insert (index, str.data->buffer, 0, str.data->size);
	}

	void prepend (const char_type* str, xp_size_t offset, xp_size_t size)
	{
		this->insert (0, str, offset, size);	
	}
	void prepend (const char_type* str)
	{
		this->insert (0, str);
	}
	void prepend (const char_type c)
	{
		this->insert (0, c);
	}
	void prepend (const ThisType& str, xp_size_t offset, xp_size_t size)
	{
		this->insert (0, str, offset, size);
	}
	void prepend (const ThisType& str)
	{
		this->insert (0, str);
	}

	void append (const char_type* str, xp_size_t offset, xp_size_t size)
	{
		this->insert (this->data->size, str, offset, size);	
	}
	void append (const char_type* str)
	{
		this->insert (this->data->size, str);
	}
	void append (const char_type c)
	{
		this->insert (this->data->size, c);
	}
	void append (const ThisType& str, xp_size_t offset, xp_size_t size)
	{
		this->insert (this->data->size, str, offset, size);
	}
	void append (const ThisType& str)
	{
		this->insert (this->data->size, str);
	}

	void appendFormat (const char_type* fmt, ...)
	{
		/*
		int n;
		if (this->data->isShared()) 
		{
			StringData* t = this->data->copy ();
			this->data->deref (); this->data = t; this->data->ref ();
		}
		xp_va_start (ap, fmt);
		while ((n = ThisType::opset.vsprintf (&this->data->buffer[this->data->size], this->data->capacity - this->data->size, fmt, ap)) <= -1)
		{
			this->data->growBy (calc_new_inc_for_growth (0));
			xp_va_end (ap);
			xp_va_start (ap, fmt);
		}
		xp_va_end (ap);
		this->data->size += n;
		*/
		xp_va_list ap;
		xp_va_start (ap, fmt);
		this->appendFormat (fmt, ap);
		xp_va_end (ap);
	}

	void appendFormat (const char_type* fmt, xp_va_list ap)
	{
		int n;
		xp_va_list save_ap;

		if (this->data->isShared()) 
		{
			StringData* t = this->data->copy ();
			this->data->deref (); this->data = t; this->data->ref ();
		}

		xp_va_copy (save_ap, ap);
		while ((n = ThisType::opset.vsprintf (&this->data->buffer[this->data->size], this->data->capacity - this->data->size, fmt, ap)) <= -1)
		{
			this->data->growBy (calc_new_inc_for_growth (0));
			xp_va_copy (ap, save_ap);
		}
		
		this->data->size += n;
	}

	void set (const char_type* str, xp_size_t offset, xp_size_t size)
	{
		this->remove ();
		this->insert (0, str, offset, size);	
	}
	void set (const char_type* str)
	{
		this->remove ();
		this->insert (0, str);
	}
	void set (const char_type c)
	{
		this->remove ();
		this->insert (0, c);
	}
	void set (const ThisType& str, xp_size_t offset, xp_size_t size)
	{
		this->remove ();
		this->insert (0, str, offset, size);
	}
	void set (const ThisType& str)
	{
		operator= (str);
	}

	void remove (xp_size_t offset, xp_size_t size)
	{
		if (size <= 0) return;
		if (offset >= this->data->size) return;
		if (size > this->data->size - offset) size = this->data->size - offset;

		if (this->data->isShared()) 
		{
			StringData* t = this->data->copy ();
			this->data->deref (); this->data = t; this->data->ref ();
		}

		char_type* p = this->data->buffer + offset;
		xp_memcpy (p, p + size, (this->data->size - offset - size + 1) * XP_SIZEOF(char_type));
		this->data->size -= size;	
	}
	void remove ()
	{
		this->remove (0, this->data->size);
	}

	void invert (xp_size_t offset, xp_size_t size)
	{
		xp_assert (offset + size <= this->data->size);
	
		if (this->data->isShared()) 
		{
			StringData* t = this->data->copy ();
			this->data->deref (); this->data = t; this->data->ref ();
		}
	
		char_type c;
		xp_size_t i = offset + size;
		for (xp_size_t j = offset; j < --i; j++) 
		{
			c = this->data->buffer[j];	
			this->data->buffer[j] = this->data->buffer[i];
			this->data->buffer[i] = c;
		}
	}
	void invert ()
	{
		this->invert (0, this->data->size);
	}

	void replace (xp_size_t offset, xp_size_t size, const char_type* str, xp_size_t soffset, xp_size_t ssize)
	{
		this->remove (offset, size);	
		this->insert (offset, str, soffset, ssize);
	}
	void replace (xp_size_t offset, xp_size_t size, const char_type* str)
	{
		this->remove (offset, size);
		this->insert (offset, str, 0, ThisType::lengthOf(str));
	}
	void replace (xp_size_t offset, xp_size_t size, const ThisType& str, xp_size_t soffset, xp_size_t ssize)
	{
		this->remove (offset, size);	
		this->insert (offset, str, soffset, ssize);
	}
	void replace (xp_size_t offset, xp_size_t size, const ThisType& str)
	{
		this->remove (offset, size);
		this->insert (offset, str);
	}

	void replaceAll (xp_size_t index, const char_type* str1, const char_type* str2)
	{
		xp_size_t len1 = ThisType::lengthOf(str1);
		xp_size_t len2 = ThisType::lengthOf(str2);
		while ((index = this->indexOf(index, str1, 0, len1)) != INVALID_INDEX) 
		{
			this->replace (index, len1, str2, 0, len2);
			index += len2;
		}
	}
	void replaceAll (const char_type* str1, const char_type* str2)
	{
		this->replaceAll (0, str1, str2);
	}
	void replaceAll (xp_size_t index, const ThisType& str1, const ThisType& str2)
	{
		while ((index = this->indexOf(index, str1)) != INVALID_INDEX) 
		{
			this->replace (index, str1.data->data->size, str2);
			index += str2.data->data->size;
		}
	}
	void replaceAll (const ThisType& str1, const ThisType& str2)
	{
		this->replaceAll (0, str1, str2);
	}

	ThisType substring (xp_size_t offset)
	{
		xp_assert (offset < this->data->size);
		return ThisType (this->data->buffer, offset, this->data->size - offset);
	}
	ThisType substring (xp_size_t offset, xp_size_t size)
	{
		xp_assert (offset + size <= this->data->size);
		return ThisType (this->data->buffer, offset, size);
	}

	xp_size_t indexOf (xp_size_t index,
		const char_type* str, xp_size_t offset, xp_size_t size) const
	{
		if (size == 0) return index;
		if (size > this->data->size) return INVALID_INDEX;
		if (index >= this->data->size) return INVALID_INDEX;
	
		/*
		char_type first = str[offset];
		xp_size_t i = index;
		xp_size_t max = this->data->size - size;
		char_type* p = this->data->buffer;
	
	loop_indexOf:
		while (i <= max && p[i] != first) i++;
		if (i > max) return INVALID_INDEX;
	
		xp_size_t j = i + 1;
		xp_size_t end = j + size - 1;
		xp_size_t k = offset + 1;
		while (j < end) {
			if (p[j++] != str[k++]) {
				i++;
				goto loop_indexOf;
			}
		}
		return i;
		*/
	
		char_type first = str[offset];
		char_type* s1 = this->data->buffer + index;
		char_type* e1 = this->data->buffer + this->data->size - size;
		char_type* p1 = s1;
	
	loop_indexOf:
		while (p1 <= e1 && *p1 != first) p1++;
		if (p1 > e1) return INVALID_INDEX;
	
		const char_type* s2 = str + offset + 1;
	
		char_type* p2 = p1 + 1;
		char_type* e2 = p2 + size - 1;
	
		while (p2 < e2) 
		{
			if (*p2++ != *s2++) 
			{
				p1++;
				goto loop_indexOf;
			}
		}

		return p1 - this->data->buffer;
	}
	xp_size_t indexOf (xp_size_t index, const char_type* str) const
	{
		return indexOf (index, str, 0, ThisType::lengthOf(str));
	}
	xp_size_t indexOf (const char_type* str, xp_size_t offset, xp_size_t size) const
	{
		return indexOf (0, str, offset, size);
	}
	xp_size_t indexOf (const char_type* str) const
	{
		return indexOf (0, str);
	}
	xp_size_t indexOf (xp_size_t index, const ThisType& str, xp_size_t offset, xp_size_t size) const
	{
		xp_assert (offset + size <= str.data->size);
		return this->indexOf (index, str.data->buffer, offset, size);
	}
	xp_size_t indexOf (xp_size_t index, const ThisType& str) const
	{
		return this->indexOf (index, str.data->buffer, 0, str.data->size);
	}
	xp_size_t indexOf (const ThisType& str, xp_size_t offset, xp_size_t size) const
	{
		xp_assert (offset + size <= str.data->size);
		return this->indexOf (0, str.data->buffer, offset, size);
	}
	xp_size_t indexOf (const ThisType& str) const
	{
		return this->indexOf (0, str.data->buffer, 0, str.data->size);
	}
	xp_size_t indexOf (xp_size_t index, char_type c) const
	{
		if (index >= this->data->size) return INVALID_INDEX;
	
		char_type* s = this->data->buffer + index;
		char_type* e = this->data->buffer + this->data->size;
	
		for (char_type* p = s; p < e; p++) 
		{
			if (*p == c) return p - s;
		}
	
		return INVALID_INDEX;
	}
	xp_size_t indexOf (char_type c) const
	{
		return indexOf (0, c);
	}

	xp_size_t lastIndexOf (xp_size_t index,
		const char_type* str, xp_size_t offset, xp_size_t size) const
	{
		if (size == 0) return index;
		if (size > this->data->size) return INVALID_INDEX;
		if (index >= this->data->size) index = this->data->size - 1;
	
		xp_size_t strLast = offset + size - 1;
		char_type last = str[strLast];
		xp_size_t min = size - 1;
		xp_size_t i = min + index;
		char_type* p = this->data->buffer;
	
	loop_lastIndexOf:
		while (i >= min && p[i] != last) 
		{
			if (i <= min) return INVALID_INDEX;
			i--;
		}

		xp_size_t j = i - 1;
		xp_size_t start = j - size + 1;
		xp_size_t k = strLast - 1;
		while (j > start) 
		{
			if (p[j--] != str[k--]) 
			{
				i--;
				goto loop_lastIndexOf;
			}
		}
		return start + 1;
	}
	xp_size_t lastIndexOf (xp_size_t index, const char_type* str) const
	{
		return this->lastIndexOf (index, str, 0, ThisType::lengthOf(str));
	}
	xp_size_t lastIndexOf (const char_type* str, xp_size_t offset, xp_size_t size) const
	{
		return this->lastIndexOf (this->data->size - 1, str, offset, size);
	}
	xp_size_t lastIndexOf (const char_type* str) const
	{
		return this->lastIndexOf (this->data->size - 1, str);
	}
	xp_size_t lastIndexOf (xp_size_t index, const ThisType& str, xp_size_t offset, xp_size_t size) const
	{
		xp_assert (offset + size <= str.data->size);
		return this->lastIndexOf (index, str.data->buffer, offset, size);
	}
	xp_size_t lastIndexOf (xp_size_t index, const ThisType& str) const
	{
		return this->lastIndexOf (index, str.data->buffer, 0, str.data->size);
	}
	xp_size_t lastIndexOf (const ThisType& str, xp_size_t offset, xp_size_t size) const
	{
		xp_assert (offset + size <= str.data->size);
		return this->lastIndexOf (this->data->size - 1, str.data->buffer, offset, size);
	}
	xp_size_t lastIndexOf (const ThisType& str) const
	{
		return this->lastIndexOf (this->data->size - 1, str.data->buffer, 0, str.data->size);
	}
	xp_size_t lastIndexOf (xp_size_t index, char_type c) const
	{
		if (index >= this->data->size) index = this->data->size - 1;

		char_type* s = this->data->buffer;
		char_type* e = this->data->buffer + index;

		for (char_type* p = e; p >= s; p--) 
		{
			if (*p == c) return p - s;
		}

		return INVALID_INDEX;
	}
	xp_size_t lastIndexOf (char_type c) const
	{
		return this->lastIndexOf (this->data->size - 1, c);
	}

	bool beginsWith (const char_type* str) const
	{
		xp_size_t idx = 0;
		while (*str != (char_type)0) {
			if (idx >= this->data->size) return false;
			if (this->data->buffer[idx] != *str) return false;
			idx++; str++;
		}
		return true;
	}

	bool beginsWith (const char_type* str, const xp_size_t len) const
	{
		const char_type* end = str + len;
		xp_size_t idx = 0;

		while (str < end) {
			if (idx >= this->data->size) return false;
			if (this->data->buffer[idx] != *str) return false;
			idx++; str++;
		}
		return true;
	}

	xp_size_t touppercase ()
	{
		if (this->data->isShared()) 
	{
			StringData* t = this->data->copy ();
			this->data->deref (); this->data = t; this->data->ref ();
		}

		return touppercase (this->data->buffer);
	}

	xp_size_t tolowercase ()
	{
		if (this->data->isShared()) 
		{
			StringData* t = this->data->copy ();
			this->data->deref (); this->data = t; this->data->ref ();
		}
		return tolowercase (this->data->buffer);
	}

	xp_size_t trim ()
	{
		if (this->data->isShared()) 
		{
			StringData* t = this->data->copy ();
			this->data->deref (); this->data = t; this->data->ref ();
		}

		this->data->size = ThisType::trim (this->data->buffer);
		return this->data->size;
	}

protected:
	mutable StringData* data;
	GrowthPolicy growth_policy;
	static OPSET opset;

private:
	static xp_size_t round_capacity (xp_size_t n) 
	{
		if (n == 0) n = 1;
		return 
			(n + (xp_size_t)DFL_CAPACITY - 1) & 
			~((xp_size_t)DFL_CAPACITY - (xp_size_t)1);
	}

	xp_size_t calc_new_inc_for_growth (xp_size_t desired_inc)
	{
		xp_size_t inc ;
		switch (this->growth_policy.type)
		{
			case GrowthPolicy::PERCENT:
				inc = (this->data->size * this->growth_policy.value) / 100;
				break;

			case GrowthPolicy::ABSOLUTE:
				inc = this->growth_policy.value;
				break;

			default:
				inc = DFL_CAPACITY;
				break;
		}	

		if (inc <= 0) inc = 1;
		if (inc < desired_inc) inc = desired_inc;
		return round_capacity (inc);
	}

public:
	//////////////////////////////////////////////////////////
	// static functions
	//////////////////////////////////////////////////////////
	static xp_size_t lengthOf (const char_type* str)
	{
		xp_size_t len = 0;
		while (*str++ != (char_type)0) len++;
		return len;
	}

	static char_type* find (const char_type* str, char_type c)
	{
		while (*str != (char_type)0) 
		{
			if (*str == c) return (char_type*)str;
			str++;
		}
		return XP_NULL;
	}

	static int compare (const char_type* s1, const char_type* s2)
	{
		while (*s1 == *s2 && *s2 != (char_type)0) s1++, s2++;
		if (*s1 > *s2) return 1;
		else if (*s1 < *s2) return -1;
		return 0;
	}
	static int compare (const char_type* s1, const char_type* s2, xp_size_t count)
	{
		if (count == 0) return 0;
		while (--count && *s1 != (char_type)0 && *s1 == *s2) s1++, s2++;
		if (*s1 > *s2) return 1;
		else if (*s1 < *s2) return -1;
		return 0;
	}
	static int compare (const char_type* s1, xp_size_t s1_count, const char_type* s2)
	{
		xp_size_t idx = 0;
		while (idx < s1_count && s2[idx] != (char_type)0 && s1[idx] == s2[idx]) idx++;
		if (idx == s1_count && s2[idx] == (char_type)0) return 0;
		if (s1[idx] == s2[idx]) return (s1_count > idx)? 1: -1;
		return (s1[idx] > s2[idx])? 1: -1;
	}
	static int compare (const char_type* s1, xp_size_t s1_count, const char_type* s2, xp_size_t s2_count)
	{
		char_type c1, c2;
		const char_type* end1 = s1 + s1_count;
		const char_type* end2 = s2 + s2_count;

		while (s1 < end1)
		{
			c1 = *s1;
			if (s2 < end2) 
			{
				c2 = *s2;
				if (c1 > c2) return 1;
				if (c1 < c2) return -1;
			}
			else return 1;
			s1++; s2++;
		}

		return (s2 < end2)? -1: 0;
	}

	static xp_size_t copy (char_type* dst, xp_size_t dsz, const char_type* src, xp_size_t ssz)
	{
		xp_assert (dsz > 0);
		xp_size_t sz = (dsz - 1 >= ssz)? ssz: dsz - 1;	
		xp_memcpy (dst, src, sz * XP_SIZEOF(char_type));
		dst[sz] = (char_type)0;
		return sz;
	}
	static xp_size_t copy (char_type* dst, xp_size_t dsz, const char_type* src)
	{
		return copy (dst, dsz, src, ThisType::lengthOf(src));
	}
	static xp_size_t copy (char_type* dst, const char_type* src)
	{
		const char_type* p = src;
		while (*p != (char_type)0) *dst++ = *p++;
		*dst = (char_type)0;	
		return p - src;
	}

	static xp_size_t tolowercase (char_type* str)
	{
		char_type* p = str;
		while (*p != (char_type)0) 
		{
			*p = ThisType::opset.toLower (*p);
			p++;
		}
		return p - str;
	}
	static xp_size_t touppercase (char_type* str)
	{
		char_type* p = str;
		while (*p != (char_type)0) 
		{
			*p = ThisType::opset.toUpper (*p);
			p++;
		}
		return p - str;
	}
	//static char_type* tolowercase (char_type* str, xp_size_t sz);
	//static char_type* touppercase (char_type* str, xp_size_t sz);
	static xp_size_t trim (char_type* str)
	{
		char_type* p = str, * s = XP_NULL, * e = XP_NULL;

		while (*p != (char_type)0) 
		{
			if (!ThisType::opset.isSpace(*p)) 
			{
				if (s == XP_NULL) s = p;
				e = p;
			}
			p++;
		}

		if (e != XP_NULL) 
		{
			e[1] = (char_type)0;
			xp_memcpy (str, s, (e - s + 2) * XP_SIZEOF(char_type));
			return e - s + 1;
		}

		str[0] = (char_type)0;
		return 0;
	}

	static xp_size_t format (char_type* buf, xp_size_t size, const char_type* fmt, ...)
	{
		xp_assert (size > 0);

		xp_va_list ap;
		xp_va_start (ap, fmt);

		int n = ThisType::opset.vsprintf (buf, size, fmt, ap);
		xp_va_end (ap);

		if (n <= -1)
		{
			buf[size - 1] = (char_type)0;
			return size - 1;
		}
		return (xp_size_t)n;
	}

	static xp_size_t formatv (char_type* buf, xp_size_t size, const char_type* fmt, xp_va_list ap)
	{
		xp_assert (size > 0);

		int n = ThisType::opset.vsprintf (buf, size, fmt, ap);
		if (n <= -1)
		{
			buf[size - 1] = (char_type)0;
			return size - 1;
		}
		return (xp_size_t)n;
	}

	static char_type* tokenize (const char_type* s, const char_type* delim, char_type** tok, xp_size_t* tok_len)
	{
		const char_type* p = s, *d;
		const char_type* sp = XP_NULL, * ep = XP_NULL;
		char_type c; 
		int delim_mode;
	
		// skip preceding space char_typeacters
		while (/* *p && */ ThisType::opset.isSpace(*p)) p++;
	
		if (delim == XP_NULL) delim_mode = 0;
		else 
		{
			delim_mode = 1;
			for (d = delim; *d; d++) 
				if (!ThisType::opset.isSpace(*d)) delim_mode = 2;
		}
	
		if (delim_mode == 0) {
		 
			// when XP_NULL is given as "delim", it has an effect of cutting
			// preceding and trailing space char_typeacters off "s".
			while ((c = *p)) 
			{
				if (!ThisType::opset.isSpace(c)) 
				{
					if (sp == XP_NULL) sp = p;
					ep = p;
				}
				p++;
			}
		}
		else if (delim_mode == 1) 
		{
			while ((c = *p)) 
			{
				if (ThisType::opset.isSpace(c)) break;
	
				if (sp == XP_NULL) sp = p;
				ep = p++;
			}
		}
		else 
		{ /* if (delim_mode == 2) { */
			while ((c = *p)) 
			{
				if (ThisType::opset.isSpace(c)) 
				{
					p++;
					continue;
				}
				for (d = delim; *d; d++) {
					if (c == *d) {
						goto exit_loop;
					}
				}
				if (sp == XP_NULL) sp = p;
				ep = p++;
			}
		}
	
	exit_loop:
		if (sp == XP_NULL) {
			*tok = XP_NULL;
			*tok_len = (xp_size_t)0;
		}
		else {
			*tok = (char_type*)sp;
			*tok_len = (xp_size_t)(ep - sp + 1);
		}
		if (c == (char_type)0) return XP_NULL;
		return (char_type*)++p;
	}

	static bool aredigits (const char_type* s)
	{
		while (*s != (char_type)0) 
		{
			if (!ThisType::opset.isDigit(*s)) return false;
			s++;
		}
		return true;
	}

	static bool aredigits (const char_type* s, xp_size_t len)
	{
		const char_type* end = s + len;
		while (s < end) 
		{
			if (!ThisType::opset.isDigit(*s)) return false;
			s++;
		}
		return true;
	}

	static bool aresigneddigits (const char_type* s)
	{
		if (*s == (char_type)'+' || *s == (char_type)'-') 
		{
			s++;
			if (*s == (char_type)0) return false;
		}

		while (*s != (char_type)0) 
		{
			if (!ThisType::opset.isDigit(*s)) return false;
			s++;
		}
		return true;
	}

	static bool aresigneddigits (const char_type* s, xp_size_t len)
	{
		const char_type* end = s + len;
		if (*s == (char_type)'+' || *s == (char_type)'-') 
		{
			s++;
			if (s >= end) return false;
		}

		while (s < end) {
			if (!ThisType::opset.isDigit(*s)) return false;
			s++;
		}
		return true;
	}

};

template <typename char_type, typename OPSET>
OPSET BaseString<char_type,OPSET>::opset;

template <typename char_type, typename OPSET> 
class BasePtrString
{
public:
	typedef BasePtrString<char_type,OPSET> ThisType;
	typedef BaseString<char_type,OPSET> StringType;

	BasePtrString (): ptr (XP_NULL), len (0) {}

	BasePtrString (const char_type* ptr): ptr (ptr)
	{
		this->len = StringType::lengthOf (ptr);
	}

	BasePtrString (const char_type* ptr, xp_size_t len): ptr (ptr), len (len) 
	{
		// do nothing
	}

	xp_size_t hashCode () const
	{
		// keep this in sync with hashCode of ThisType
		return Hashable::hashCode (this->ptr, this->len * XP_SIZEOF(char_type));
	}

	bool operator== (const ThisType& ps) const
	{
		return StringType::compare (this->ptr, this->len, ps.ptr, ps.len) == 0;
	}

	bool operator!= (const ThisType& ps) const
	{
		return !operator== (ps);
	}

	bool operator== (const StringType& s) const
	{
		return StringType::compare (this->ptr, this->len, s.buffer(), s.length()) == 0;
	}

	bool operator!= (const StringType& s) const
	{
		return !operator== (s);
	}

	operator const char_type* () const
	{
		return this->ptr;
	}

	xp_size_t length() const
	{
		return this->len;
	}

protected:
	const char_type* ptr;
	xp_size_t        len;
};

XP_END_NAMESPACE2 (xp, bas)

#endif
